package edu.npu.GraphQuery;

import java.io.DataInput;
import java.io.DataOutput;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Set;

import org.apache.hadoop.io.LongWritable;
import org.apache.hadoop.io.WritableComparable;

import edu.npu.GraphIndex.CntVid;

//最短路径图查询算法(Jiawei Han文章的实现)
public class SPGraphQuery {
	int HOP = 3;//最短路径的跳数
	Map<Long, List<Long>> qGraph; //大图G和查询图Q
	Map<String, List<Long>> lookupTable;
	Map<Long, String> qLabel;
	Map<Long, Map<Integer, Map<String, CntVid>>> histogramIndex, qHistogramIndex;
	//某个节点在某个距离的最短路径记录
	Map<Long, Map<Integer, List<ShortestPath>>> qShortestPath =
		new HashMap<Long, Map<Integer,List<ShortestPath>>>();
	Set<QEdge> qEdgeSet = new HashSet<SPGraphQuery.QEdge>();//查询图的边构成的集合
	//查询节点和候选节点对应的最短路径,与candidate对应
	Map<Long, List<List<ShortestPath>>> paths = new HashMap<Long, List<List<ShortestPath>>>();
	Map<Long, List<Long>> candidate = new HashMap<Long, List<Long>>();//候选节点映射
	Map<Long, List<List<Double>>> selectivities = new HashMap<Long, List<List<Double>>>();
	HashSet<HashSet<QEdge>> resultSet = new HashSet<HashSet<QEdge>>();

	
	public SPGraphQuery() {
		
	}
	public SPGraphQuery(Map<Long, List<Long>> qGraph, Map<String, List<Long>> lookupTable, 
			Map<Long, String> qLabel, Map<Long, Map<Integer, Map<String, CntVid>>> histogramIndex, 
			Map<Long, Map<Integer, Map<String, CntVid>>> qHistogramIndex) {
		this.qGraph = qGraph;
		this.lookupTable = lookupTable;
		this.qLabel = qLabel;
		this.histogramIndex = histogramIndex;
		this.qHistogramIndex = qHistogramIndex;
		//对于查询图每个节点对应的最短路径生成索引
		this.spIndexInit();
		//对查询图的边生成边的集合
		this.eSetInit();
		this.candidateSelection();
		this.candiPathInit();
	}
	//查询主函数
	public List<Map<QEdge, QEdge>> queryProcessing() {
		long vStar = 0;
		int minVSize = Integer.MAX_VALUE;
		ShortestPath pu = null;
		Map<ShortestPath, ShortestPath> initiation = null;
		List<ShortestPath> spCollection = new ArrayList<ShortestPath>();
		List<Map<QEdge, QEdge>> result = new ArrayList<Map<QEdge,QEdge>>();
		
		for(Entry<Long, List<Long>> entry : candidate.entrySet()) {
			if(entry.getValue().size() < minVSize) {
				vStar = entry.getKey();
				minVSize = entry.getValue().size();
			}
		}
		for(int i = 0; i < candidate.get(vStar).size(); i++) {
			for(List<ShortestPath> spList : paths.get(vStar)) {
				spCollection.addAll(spList);
			}
			pu = maxSelectivity(spCollection);
			initiation = new HashMap<ShortestPath, ShortestPath>();
			recursiveSearch(pu, initiation, result);
			spCollection.clear();
		}
		return result;
	}
	//递归搜索
	public void recursiveSearch(ShortestPath pu, Map<ShortestPath, ShortestPath> i, 
			List<Map<QEdge, QEdge>> result) {
		ShortestPath iPu = null, _pu = null;
		Iterator<ShortestPath> it = nextInstantiation(pu);
		List<ShortestPath> minS = new ArrayList<ShortestPath>();
		Set<Long> nodes = new HashSet<Long>();
		while(it.hasNext()) {
			iPu = it.next();
			if(!isJoinable(i, pu, iPu))
				continue;
			i.put(new ShortestPath(pu), new ShortestPath(iPu));
			
			if(isCovered(i.keySet())) {
				HashSet<QEdge> gEdgeSet = new HashSet<QEdge>(); 
				for(Entry<ShortestPath, ShortestPath> entry : i.entrySet()) {
					gEdgeSet.addAll(entry.getValue().path2edge());
				}
				if(!resultSet.contains(gEdgeSet)) {
					resultSet.add(gEdgeSet);
					Map<QEdge, QEdge> map = new HashMap<SPGraphQuery.QEdge, SPGraphQuery.QEdge>();
					for(Entry<ShortestPath, ShortestPath> entry : i.entrySet()) {
						for(int n = 0; n < entry.getKey().path.size() - 1; n++) {
							QEdge qEdge = new QEdge(entry.getKey().path.get(n), 
									entry.getKey().path.get(n + 1));
							if(map.containsKey(qEdge))
								continue;
							QEdge gEdge = new QEdge(entry.getValue().path.get(n),
									entry.getValue().path.get(n + 1));
							map.put(qEdge, gEdge);
						}
					}
					result.add(map);
				}
			} else {
				for(ShortestPath sp : i.keySet()) {
					nodes.addAll(sp.path);
				}
				for (long node : nodes) {
					for (List<ShortestPath> pList : paths.get(node)) {
						for (ShortestPath p : pList) {
							if (!i.keySet().contains(p) && !minS.contains(p))
								minS.add(p);
						}
					}
					_pu = maxSelectivity(minS);
					if (_pu == null) {
						continue;
					}
					recursiveSearch(_pu, i, result);
					minS.clear();
				}
			}
			i.remove(pu);
		}
//		i.remove(pu);
	}
	
	//路径实例化
	public Iterator<ShortestPath> nextInstantiation(ShortestPath pu) {
		return new PathIterator(pu);
	}
	//是否可以join
	public boolean isJoinable(Map<ShortestPath, ShortestPath> i, 
			ShortestPath pu, ShortestPath iPu) {
		List<Long> qRetain = null, gRetain = null;
		for(Entry<ShortestPath, ShortestPath> entry : i.entrySet()) {
			qRetain = new ArrayList<Long>(entry.getKey().path);
			qRetain.retainAll(pu.path);
			gRetain = new ArrayList<Long>(entry.getValue().path);
			gRetain.retainAll(iPu.path);
			if(qRetain.size() != gRetain.size())
				return false;
		}	
		return true;
	}
	//查找selectivity的最小值
	public ShortestPath maxSelectivity(List<ShortestPath> paths) {
		if(paths.size() == 0)
			return null;
		double maxSelectivity = Double.MIN_VALUE;
		double select = 0;
		ShortestPath maxSP = null;
		for(ShortestPath p : paths) {
			select = this.selectivityCalc(p);
			if(select > maxSelectivity) {
				maxSP = p;
				maxSelectivity = select;
			}
		}
		return maxSP;
	}
	//建立查询节点和候选节点的路径映射
	public void candiPathInit() {
		int kstar = 0;
		long node = -1;
		for(Entry<Long, List<Long>> entry : candidate.entrySet()) {
			node = entry.getKey();
			if(!paths.containsKey(entry.getKey()))
				paths.put(node, new ArrayList<List<ShortestPath>>());
			for(int i = 0; i < entry.getValue().size(); i++) {
				paths.get(node).add(new ArrayList<ShortestPath>());
				kstar = kStarCalc(entry.getValue().get(i), node);
				for(Entry<Integer, List<ShortestPath>> e : qShortestPath.get(node).entrySet()) {
					if(e.getKey() <= kstar) {
						for(ShortestPath sp : e.getValue()) {
							paths.get(node).get(i).add(new ShortestPath(sp));
						}
					}
				}
			}
		}
	}
	//建立查询图的边集合
	public void eSetInit() {
		for(Entry<Long, List<Long>> entry : qGraph.entrySet()) {
			for(long node : entry.getValue()) {
				QEdge edge = new QEdge(entry.getKey(), node);
				if(!qEdgeSet.contains(edge))
					qEdgeSet.add(edge);
			}
		}
	}
	
	//所有shortestpath的索引建立
	public void spIndexInit() {
		//lvlSize记录当前一层的节点数量,
		//nxtLvlSize记录下一层的节点数量,
		//level记录当前遍历的层数
		int lvlSize = 0, nxtLxlSize = 0, level = 0;
		ShortestPath sp = null;
		long expandNode = -1;
		List<Long> traversed = new ArrayList<Long>();
		//tmpTraversed的作用在于对于同样的最短路径,
		//同一层的都在tmpTraversed中,这样就不会遗漏同样长度的最短路径,
		//在遍历完一层后将tmpTravered一起加入到traversed中
		List<Long> tmpTraversed = new ArrayList<Long>();
		Queue<ShortestPath> queue = new LinkedList<ShortestPath>();
		
		//对query中的每个节点做遍历,计算每个节点的最短路径
		for(long node : this.qHistogramIndex.keySet()) {
			queue.add(new ShortestPath(node));
			lvlSize++;
			if(!qShortestPath.containsKey(node))
				qShortestPath.put(node, new HashMap<Integer, List<ShortestPath>>());
			while(!queue.isEmpty()) {
				sp = queue.poll();
				expandNode = sp.path.get(sp.path.size() - 1);
				lvlSize--;
				//判断是否遍历过
				if(!traversed.contains(expandNode)) {
					//加入已遍历节点
					tmpTraversed.add(expandNode);
					//加入到最短路径的记录中
					if (level != 0) {
						if (!qShortestPath.get(node).containsKey(level))
							qShortestPath.get(node).put(level,
									new ArrayList<ShortestPath>());
						qShortestPath.get(node).get(level).add(sp);
					}

					// 加入临接点,是下一层节点了,所以不能在traversed中,
					// 但是可以在tmpTraversed和队列中,因为存在长度相同的最短路径;
					for (long neigh : qGraph.get(expandNode)) {
						if (traversed.contains(neigh))
							continue;
						ShortestPath neighSP = new ShortestPath(sp);
						neighSP.addNode(neigh);
						queue.add(neighSP);
						nxtLxlSize++;
					}
				}
				
				//一层遍历结束
				if (lvlSize == 0) {
					lvlSize = nxtLxlSize;
					nxtLxlSize = 0;
					level++;
					for(long n : tmpTraversed){
						if(!traversed.contains(n))
							traversed.add(n);
					}
					tmpTraversed.clear();
				}
			}
			//遍历完一个节点,清空所有的变量
			lvlSize = 0; nxtLxlSize = 0; level = 0;
			queue.clear();
			traversed.clear();
			tmpTraversed.clear();
		}
	}
	
	public boolean isNSContainment(Map<Integer, Map<String, CntVid>> gHistogram, 
			Map<Integer, Map<String, CntVid>> qHistogram) {
		int n = 0;
		Map<String, Integer> count = new HashMap<String, Integer>();
		for(String label : qLabel.values()) {
			count.put(label, 0);
		}
		for(int k = 1; k <= HOP && qHistogram.containsKey(k); k++) {
			for(String label : qLabel.values()) {
				n = count.get(label);
				if(gHistogram.containsKey(k) &&
						gHistogram.get(k).containsKey(label))
					count.put(label, n + gHistogram.get(k).get(label).count);
				if(qHistogram.containsKey(k) &&
						qHistogram.get(k).containsKey(label) && 
						qHistogram.get(k).get(label).count > count.get(label)) {
					return false;
				}
				n = count.get(label);
				if(qHistogram.containsKey(k) &&
						qHistogram.get(k).containsKey(label))
					count.put(label, n - qHistogram.get(k).get(label).count);
			}
		}
		return true;
	}
	public void candidateSelection() {
		for(Entry<Long, String> entry : qLabel.entrySet()) {
			if(!candidate.containsKey(entry.getKey()))
				candidate.put(entry.getKey(), new ArrayList<Long>());
			for(long gNode : lookupTable.get(entry.getValue())) {
				if(isNSContainment(histogramIndex.get(gNode), qHistogramIndex.get(entry.getKey())))
					candidate.get(entry.getKey()).add(gNode);
			}
		}
	}
	public boolean isCovered(Set<ShortestPath> spSet) {
		Set<QEdge> tmpEdge = null;
		ShortestPath spMax = null;
		Set<QEdge> edgeSet = new HashSet<SPGraphQuery.QEdge>(qEdgeSet);
		Set<QEdge> eSPSet = new HashSet<SPGraphQuery.QEdge>();
		for(ShortestPath sp : spSet) {
			eSPSet.addAll(sp.path2edge());
		}

		int max = 0;
		while(!edgeSet.isEmpty()) {
			if(eSPSet.isEmpty())
				return false;
			for(ShortestPath sp : spSet) {
				tmpEdge = sp.path2edge();
				tmpEdge.retainAll(edgeSet);
				if(tmpEdge.size() > max) {
					max = tmpEdge.size();
					spMax = sp;
				}
			}
			edgeSet.removeAll(spMax.path2edge());
			eSPSet.removeAll(spMax.path2edge());
			max = 0;
		}
		return true;
	}
	//selectivity的计算
	public double selectivityCalc(ShortestPath path) {
		double selectivity = 0;
		double top = Math.pow(2, path.path.size());
		double bottom = 1.0;
		for(long node : path.path) {
			bottom *= candidate.get(node).size();
		}
		selectivity = top / bottom;
		return selectivity;
	}
	//计算查询图和原图都是最段路径的最小长度
	public int kStarCalc(long gNode, long qNode) {
		int kstar = 0;
		for(Entry<Integer, Map<String, CntVid>> entry : 
				qHistogramIndex.get(qNode).entrySet()) {
			kstar = entry.getKey();
			for(Entry<String, CntVid> e : entry.getValue().entrySet()) {
				if(histogramIndex.get(gNode).get(entry.getKey()).get(e.getKey()).count >
						e.getValue().count)
					return kstar;
			}
		}
		return kstar;
	}
	//图中包含的边, 用来做集合覆盖的元素使用
	static class QEdge implements WritableComparable<QEdge>{
		
		long src, dist;
		public QEdge() {
			src = 0;
			dist = 0;
		}
		public QEdge(long src, long dist) {
			if(src > dist) {
				this.src = dist;
				this.dist = src;
			} else {
				this.src = src;
				this.dist = dist;
			}
		}
		
		@Override
		public int compareTo(QEdge other) {
			if(src > other.src) {
				return 1;
			} else {
				if(src < other.src)
					return -1;
			}
			return dist > other.dist ? 1 : -1;
		}
		@Override
		public void readFields(DataInput input) throws IOException {
			LongWritable src = new LongWritable();
			LongWritable dist = new LongWritable();
			src.readFields(input);
			dist.readFields(input);
			this.src = src.get();
			this.dist = dist.get();
		}
		@Override
		public void write(DataOutput output) throws IOException {
			new LongWritable(src).write(output);
			new LongWritable(dist).write(output);
		}
		
		@Override
		public String toString() {
			return src + "->" + dist;
		}
		@Override
		public boolean equals(Object obj) {
			QEdge other = (QEdge) obj;
			if(this.src != other.src)
				return false;
			if(this.dist != other.dist)
				return false;
			return true;
		}
		@Override
		public int hashCode() {
			return (int) (src * 13 + dist);
		}
		
	}
	//路径实例化遍历器
	class PathIterator implements Iterator<ShortestPath> {
		ShortestPath qPath = null;
		long gNode;
		//用来记录遍历的状态
		int[] state; 
		ShortestPath result = new ShortestPath();
		List<Long> cache = new ArrayList<Long>();
		
		public PathIterator() {
			
		}
		public PathIterator(ShortestPath pu) {
			qPath = pu;
			gNode = pu.path.get(0);
			state = new int[pu.path.size() - 1];
		}
		@Override
		public boolean hasNext() {
			return pathInitiation();
		}

		@Override
		public ShortestPath next() {
			if(qPath.path.size() > result.path.size())
				result.path.add(cache.remove(0));
			else
				result.path.set(qPath.path.size() - 1, cache.remove(0));
			return new ShortestPath(result);
		}

		@Override
		public void remove() {
			// TODO Auto-generated method stub
			
		}
		//查询图节点qNode的候选节点集合和节点u中qNode对应标签距离为1的NS节点集合是否相交
		public boolean isExist(long qNode, long gNode) {
			List<Long> qCandi = candidate.get(qNode);
			List<Long> gCandi = new ArrayList<Long>(histogramIndex.get(gNode).get(1).get(qLabel.get(qNode)).vid);
			gCandi.retainAll(qCandi);
			if(!gCandi.isEmpty())
				return true;
			return false;
		}
		public void cache(long qNode, long gNode) {
			List<Long> qCandi = candidate.get(qNode);
			cache = new ArrayList<Long>(histogramIndex.get(gNode).get(1).get(qLabel.get(qNode)).vid);
			cache.retainAll(qCandi);
		}
		//利用state记录遍历的状态
		public boolean pathInitiation() {
			if(!cache.isEmpty()) {
				return true;
			}
			for(int num = 0; num < state.length; num++) {
				if(num == -1) {
					return false;
				} 
				//遍历num层超过界限了
				if(state[num] == candidate.get(qPath.path.get(num)).size()) {
					for (int j = num; j < state.length; j++) {
						state[j] = 0;
					}
					num -= 2;
					continue;
				}
				//如果能够将路径中的节点实例化
				if(isExist(qPath.path.get(num + 1), 
						candidate.get(qPath.path.get(num)).get(state[num]))) {
					if(num == state.length - 1)
						cache(qPath.path.get(num + 1), 
								candidate.get(qPath.path.get(num)).get(state[num]));
					if(result.path.size() > num)
						result.path.set(num, candidate.get(qPath.path.get(num)).get(state[num]++));
					else
						result.path.add(candidate.get(qPath.path.get(num)).get(state[num]++));
				} else {
					state[num--]++;
				}
			}
			return true;
		}
	}
	public static void main(String[] args) {
		QEdge qe1 = new QEdge(1, 2);
		QEdge qe2 = new QEdge(2, 1);
		System.out.println(qe1.equals(qe2));
	}
}
